\documentclass[17pt,headrule,footrule,fleqn]{beamer}
\usepackage{latexsym}
%\usepackage[a4paper]{geometry}
%\geometry{top=3.0cm}
%\geometry{left=3.0cm}
%\geometry{right=3.0cm}
%\geometry{bottom=3.0cm}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage[boxed]{algorithm}
\usepackage[noend]{algorithmic}
\usepackage{totpages}

%% Locale
\newcommand{\universitas}{Universitas Trisakti}
\newcommand{\fakultas}{Fakultas Teknologi Industri}
\newcommand{\programstudi}{Teknik Informatika}
\newcommand{\namakuliah}{Desain dan Analisa Algoritme}
\newcommand{\kodekuliah}{IKL343}
\newcommand{\tipeujian}{Kuis 1}
\newcommand{\semester}{Semester Gasal 2007/2008}
\newcommand{\mySignature}{$\alpha \gamma \dot \beta$}
\newcommand{\waktuujian}{20 menit}
\newcommand{\sifatujian}{-}
\newcommand{\dosenkoordinator}{(Anung B. Ariwibowo, M.Kom)}
\newcommand{\ralat}[1]{\textbf{(RALAT: #1)}}

%% header
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
%% \fancyhead[CO,CE]{\resizebox*{0.7cm}{!}{\includegraphics{debcor08}}}
\fancyhead[L]{{\textsf {\small \rightmark}}}
%\fancyhead[R]{{\textsf {\small \leftmark}}}
\fancyhead[R]{\namakuliah \\ \kodekuliah}
%\fancyfoot[C]{\bfseries {\small {\textsf Halaman \thepage{}
%  dari \ref{TotPages}}}}
\fancyfoot[L]{\small {\textsf Halaman \thepage{}
  dari \ref{TotPages}}}
\fancyfoot[R]{\mySignature}
\renewcommand{\headrulewidth}{0.2pt}
\renewcommand{\footrulewidth}{0.2pt}

\title{Bab 1: Analisa Algoritme}
\author{Anung B. Ariwibowo}
\date{}

\begin{document}
	\begin{frame}
	\frametitle{Ilustrasi}
  \begin{itemize}
    \item Beberapa algoritme memiliki kinerja lebih baik daripada algoritme lain
    \item Perbedaan kinerja lebih terlihat jika algoritme-algoritme tersebut diimplementasikan pada perangkat keras dengan spesifikasi berbeda
  \end{itemize}
  \end{frame}
  
  \begin{frame}
  \frametitle{Ilustrasi}
  \begin{itemize}
    \item Contoh:
    \begin{itemize}
      \item Insertion sort pada Super Komputer
      \item Merge Sort pada PC
      \item Jumlah data: 100 juta bilangan
      \item Kinerja super komputer: 100 juta instruksi per detik
      \item Kinerja PC: 1 juta instruksi per detik
    \end{itemize}
    \item Implementasi Insertion-sort menghasilkan \(2n^2\) instruksi
    \item Implementasi Merge-sort menghasilkan \(50 n \lg n\) instruksi
  \end{itemize}
  \end{frame}
  
  
  \begin{frame}
  \frametitle{Ilustrasi}
  \begin{itemize}
    \item Perbandingan waktu:
    \begin{itemize}
    	\item Super komputer:
				\[
				\frac{2 \cdot (10^6)^2 \; \mathrm{instruksi}}{10^8 \mathrm{instruksi
				  \; per \; detik}} = 20.000 \; \mathrm{detik}
				\]
			\item PC:
				\[
				\frac{50 \cdot 10^6 \lg 10^6 \; \mathrm{instruksi}}{10^6 \;
				  \mathrm{instruksi \; per \; detik}} \approx 1.000 \; \mathrm{detik}
				\]
    \end{itemize}
    \item Kesimpulan: PC 20 kali lebih cepat daripada Super komputer!
    \item Pertanyaan: dari mana jumlah instruksi untuk algoritme sorting dihitung? Kenapa bentuk rumusnya \(2n^2\) dan \(50 n \lg n\)? Kenapa bukan yang lain?
  \end{itemize}
  \end{frame}
  
  \begin{frame}
  \frametitle{Perhitungan Jumlah Instruksi sebuah Algoritme}
  \begin{itemize}
    \item Bohm-Jacopini: Instruksi-instruksi yang menyusun setiap program bisa dikelompokkan menjadi tiga:
    \begin{itemize}
      \item Sekuensial
      \item Percabangan / \emph{Selection}
      \item Perulangan / \emph{Repetition; Loop}
    \end{itemize}
  \end{itemize}
  \end{frame}
  
  
  \begin{frame}{Jumlah Instruksi Konstan}
		\begin{algorithmic}[1]
		  \STATE Proc1 (R, S)
		  \STATE r \(\leftarrow\) R
		  \STATE s \(\leftarrow\) S
		\end{algorithmic}
	\end{frame}
	
	
	\begin{frame}{Jumlah Instruksi Percabangan}
		\begin{algorithmic}[1]
		  \STATE Proc2 (a, b)
		  \STATE int s, j
		  \IF{\((a < b)\)}
		    \STATE s \(\leftarrow\) a
		  \ELSE
		    \STATE s \(\leftarrow\) b
		    \STATE j \(\leftarrow\) 9
		  \ENDIF
		  \STATE return s
		\end{algorithmic}
	\end{frame}
	
	
	\begin{frame}{Jumlah Instruksi Perulangan (dengan batas tetap)}
		\begin{algorithmic}[1]
		  \FOR{\(i \leftarrow 0 \ \mathrm{to} \ 13\)}
		    \STATE \(m_i \leftarrow i\)
		  \ENDFOR
		\end{algorithmic}
	\end{frame}
	
	
	\begin{frame}{Jumlah Instruksi Perulangan Bersarang}
		\begin{algorithmic}[1]
		  \FOR{\(i \leftarrow 0 \ \mathrm{to} \ 13\)}
		    \FOR{\(j \leftarrow 0 \ \mathrm{to} \ n\)}
		      \STATE \(m_{i,j} \leftarrow j\)
		    \ENDFOR
		  \ENDFOR
		\end{algorithmic}
	\end{frame}
	
	
	\begin{frame}{Jumlah Instruksi Perulangan Bersarang (2)}
		\begin{algorithmic}[1]
		  \FOR{\(i \leftarrow 0 \ \mathrm{to} \ n\)}
		    \FOR{\(j \leftarrow 0 \ \mathrm{to} \ 7\)}
		      \STATE \(m_{i,j} \leftarrow j\)
		    \ENDFOR
		  \ENDFOR
		\end{algorithmic}
	\end{frame}
	
	
	\begin{frame}{Jumlah Instruksi Perulangan Linier}
		\begin{algorithmic}[1]
		  \REQUIRE{\(v\) adalah sebuah larik}
		  \REQUIRE{\(n\) adalah panjang dari larik \(v\)}
		  \STATE \(m \leftarrow v_1\)
		  \FOR{\(i \leftarrow 0 \ \mathrm{to} \ n-1\)}
		    \IF{\(v_i < m\)}
		      \STATE \(m \leftarrow v_i\)
		    \ENDIF
		  \ENDFOR
		  \STATE return \(m\)
		\end{algorithmic}
	\end{frame}
	
	
	\begin{frame}{Jumlah Instruksi Perulangan Linier (2)}
		\begin{algorithmic}[1]
		  \REQUIRE{\(n\), bilangan bulat yang ingin diuji keprimaannya}
		  \FOR{\(i \leftarrow 2 \ \mathrm{to} \ i \times i \leq n\)}
		    \IF{\(n \ \mathrm{modulo} \ i = 0\)}
		      \STATE return {\tt FALSE}
		    \ENDIF
		  \ENDFOR
		  \STATE return {\tt TRUE}
		\end{algorithmic}
	\end{frame}
\end{document}
